package org.algorithm.Sort;

public class HeapSort3 {


    public void sort(int[] arr) {
        int n = arr.length;
        makeHeapTree(arr);

        for (int i = n - 1; i > 0; i--) {
            swap(arr, i, 0);

            heapify(arr,0,i);
        }
    }


    public void makeHeapTree(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
    }

    public void heapify(int[] arr, int index, int n) {

        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;

        int maxIndex = index;

        if (leftIndex < n && arr[leftIndex] > arr[maxIndex]) {
            maxIndex = leftIndex;
        }

        if (rightIndex < n && arr[rightIndex] > arr[maxIndex]) {
            maxIndex = rightIndex;
        }

        if (maxIndex != index) {
            swap(arr,index,maxIndex);
            heapify(arr, maxIndex, n);
        }
    }


    private void swap(int[] arr, int index1, int index2) {
            int temp = arr[index1];
            arr[index1]=arr[index2];
            arr[index2]=temp;
    }

    public static void main(String[] args) {
        HeapSort3 test = new HeapSort3();

        int [] arr = {1,6,3,7,5,100,68};
        test.sort(arr);

        for (int num:arr) {
            System.out.println(num);
        }
    }

}
